package sort;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/8
 * 插入排序
 */
public class Insert {

    /*
   插入排序:
       1.前半部分有序,后半部分无序
       2.遍历无序的部分,将遍历到的元素插入有序序列中的适当位置
    */
    public int[] InsertSort(int[] arr) {


        //1.找到无序的数组是从那个索引开始的
        int startIndex = -1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[i + 1]) {
                startIndex = i + 1;
                break;
            }
        }

        //2.遍历从startIndex开始到最后一个元素,依次得到无序的无序的数据中每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //记录当前要插入数据的索引
            int j = i;

            while (j > 0 && arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }

        return arr;
    }
}
